package LeetCode刷题;

import java.util.Stack;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2022-01-03 10:11
 * @description: Functions of this class is
 * 民间优化解法：
 * class Solution {
 *     public boolean validateStackSequences(int[] pushed, int[] popped) {
 *         Stack<Integer> stack = new Stack<>();
 *         int i = 0;
 *         for(int num : pushed) {
 *             stack.push(num); // num 入栈
 *             while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
 *                 stack.pop();
 *                 i++;
 *             }
 *         }
 *         return stack.isEmpty();
 *     }
 * }
 **/
public class 栈的压入and弹出顺序 {
    public static void main(String[] args) {

    }

    /**
     * 要每push一次就判断一次!!!!!!!!!!!!!!!!所以push操作要在弹出循环判断的前面
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len1=pushed.length;
        int len2=popped.length;
        if(len1==0&&len2==0||(len1==1&&len2==1&&pushed[0]==popped[0])){
            return true;
        }
        if(len1!=len2){
            return false;
        }
        Stack<Integer> stack=new Stack<Integer>();
        int j=0;
        for(int i=0;i<len1;i++){
            while(!stack.isEmpty()&&stack.peek()==popped[j]){
                //就判断下当前栈顶元素是否等于弹出数组的当前元素
                j++;
                stack.pop();
                //相等的话就弹出数字
            }
            stack.push(pushed[i]);//否则的话就入栈元素！！！！！！！！！！这一步我写的不好，应该先进性入栈，你在上面的循环判断下面入栈的话容易导致
            //导致出了for循环还没有判断完毕，所以应该要每push一次就判断一次
        }
        //入栈数组都入栈之后，可能出栈数组还没有完全判断完
        while(!stack.isEmpty()&&j<len2){
            if(stack.peek()!=popped[j]){
                return false;
            }
            stack.pop();
            j++;
        }
        return stack.isEmpty()&&j==len2;//最后看出栈数组是否都出完栈，同时栈是否为空
    }
}